#
# @lc app=leetcode.cn id=153 lang=python3
#
# [153] 寻找旋转排序数组中的最小值
#

# @lc code=start
from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        # 可能是全部有序的数据
        if nums[left] < nums[right]:
            return nums[left]
        
        while left < right:
            mid = (left + right)//2
            if nums[mid] > nums[left]:
                left = mid
            elif nums[mid] < nums[right]:
                right = mid 
            else:
                # 当上面两个都不满足的时候的时候，说明mid和left或者right重合了
                if nums[left] < nums[right]:
                    return nums[left]
                else:
                    return nums[right]
        return nums[left]
# Solution().findMin([4,5,6,7,0,1,2])     
# @lc code=end

